SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Communication-avoiding algorithm</title>

</head>

Communication-avoiding algorithm

</h1>

</header>

Communication-avoiding algorithms minimize movement of data within a <a href="Memory_hierarchy" title="Memory hierarchy">memory hierarchy</a> for improving its running-time and energy consumption. These minimize the total of two costs (in terms of time and energy): arithmetic and communication. Communication, in this context refers to moving data, either between levels of memory or between multiple processors over a network. It is much more expensive than arithmetic.<a href="#cite_note-Demmel_2012-1">[1]</a>

<div class="mw-heading mw-heading2"><h2 id="Formal_theory">Formal theory</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Two-level_memory_model">Two-level memory model</h3></div>

A common computational model in analyzing communication-avoiding algorithms is the two-level memory model:

<ul><li>There is one processor and two levels of memory.</li>

<li>Level 1 memory is infinitely large. Level 0 memory ("cache") has size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy">.</li>

<li>In the beginning, input resides in level 1. In the end, the output resides in level 1.</li>

<li>Processor can only operate on data in cache.</li>

<li>The goal is to minimize data transfers between the two levels of memory.</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Matrix_multiplication">Matrix multiplication</h3></div>

<a href="#cite_note-2">[2]</a> Corollary 6.2:

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_theorem" style="">

Theorem—Given matrices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,B,C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A,B,C}</annotation>

</semantics>

</math><img src="./0ce2acf22b93dfbd22373336bd9c22dbd98a49d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.341ex; height:2.509ex;" alt="{\displaystyle A,B,C}" loading="lazy"> of sizes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times m,m\times k,n\times k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times m,m\times k,n\times k}</annotation>

</semantics>

</math><img src="./982c4be607217a75f95745f9cfee72013ac4d691.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.882ex; height:2.509ex;" alt="{\displaystyle n\times m,m\times k,n\times k}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle AB+C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle AB+C}</annotation>

</semantics>

</math><img src="./73f4e67f57fa1d341ac4ffcef32ba8e6ccf9f910.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.114ex; height:2.343ex;" alt="{\displaystyle AB+C}" loading="lazy"> has communication complexity <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\max(mkn/M^{1/2},mk+kn+mk))}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega (\max(mkn/M^{1/2},mk+kn+mk))}</annotation>

</semantics>

</math><img src="./fe0d2003f9c796bce46c9996ac751955ef82ed54.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.452ex; height:3.343ex;" alt="{\displaystyle \Omega (\max(mkn/M^{1/2},mk+kn+mk))}" loading="lazy">.

This lower bound is achievable by <a class="mw-selflink-fragment" href="#Matrix_multiplication_example">tiling matrix multiplication</a>.

</div>

More general results for other numerical linear algebra operations can be found in.<a href="#cite_note-3">[3]</a> The following proof is from.<a href="#cite_note-4">[4]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .math_proof{border:thin solid #aaa;margin:1em 2em;padding:0.5em 1em 0.4em}@media(max-width:500px){.mw-parser-output .math_proof{margin:1em 0;padding:0.5em 0.5em 0.4em}}

/* end https://en.wikipedia.org/ */

</style><div class="math_proof" style="">Proof

We can draw the computation graph of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D=AB+C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D=AB+C}</annotation>

</semantics>

</math><img src="./9e37c043e4ed57553aa8cabda7939e794d15b7fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:13.137ex; height:2.343ex;" alt="{\displaystyle D=AB+C}" loading="lazy"> as a cube of lattice points, each point is of form <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (i,j,k)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (i,j,k)}</annotation>

</semantics>

</math><img src="./ca15aed635d1550057e6ea4cc1a5d125d225706f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.849ex; height:2.843ex;" alt="{\displaystyle (i,j,k)}" loading="lazy">. Since <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]}">

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]}</annotation>

</semantics>

</math><img src="./0cac33af611126fc1c4c482c88ffc62682d5cc2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:34.146ex; height:5.843ex;" alt="{\displaystyle D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]}" loading="lazy">, computing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle AB+C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle AB+C}</annotation>

</semantics>

</math><img src="./73f4e67f57fa1d341ac4ffcef32ba8e6ccf9f910.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.114ex; height:2.343ex;" alt="{\displaystyle AB+C}" loading="lazy"> requires the processor to have access to each point within the cube at least once. So the problem becomes covering the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle mnk}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle mnk}</annotation>

</semantics>

</math><img src="./448cba7297ad65715ed5e36f9bcdf496538af7c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.646ex; height:2.176ex;" alt="{\displaystyle mnk}" loading="lazy"> lattice points with a minimal amount of communication.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is large, then we can simply load all <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle mn+nk+mk}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle mn+nk+mk}</annotation>

</semantics>

</math><img src="./5b9c1a366684cf21449b420812320c544706b759.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:14.973ex; height:2.343ex;" alt="{\displaystyle mn+nk+mk}" loading="lazy"> entries then write <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle nk}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle nk}</annotation>

</semantics>

</math><img src="./89aeba53b00a81ae0496ccdc34536a6a1dcf1457.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.606ex; height:2.176ex;" alt="{\displaystyle nk}" loading="lazy"> entries. This is uninteresting.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> is small, then we can divide the minimal-communication algorithm into separate segments. During each segment, it performs exactly <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> reads to cache, and any number of writes from cache.

During each segment, the processor has access to at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2M}</annotation>

</semantics>

</math><img src="./beac4fab89c7f2b8472b8a83005f935d425b31de.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.605ex; height:2.176ex;" alt="{\displaystyle 2M}" loading="lazy"> different points from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A,B,C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A,B,C}</annotation>

</semantics>

</math><img src="./0ce2acf22b93dfbd22373336bd9c22dbd98a49d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.341ex; height:2.509ex;" alt="{\displaystyle A,B,C}" loading="lazy">.

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> be the set of lattice points covered during this segment. Then by the <a href="Loomis%E2%80%93Whitney_inequality" title="Loomis–Whitney inequality">Loomis–Whitney inequality</a>,

</mrow>

</mrow>

<msqrt>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|\leq {\sqrt {|\pi _{1}(E)||\pi _{2}(E)||\pi _{3}(E)|}}}</annotation>

</semantics>

</math>

with constraint <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{i}|\pi _{i}(E)|\leq 2M}">

</mrow>

</munder>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i}|\pi _{i}(E)|\leq 2M}</annotation>

</semantics>

</math><img src="./1e5ef3867ac2ab865ff608450b6f5e70219a0e77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.449ex; height:5.509ex;" alt="{\displaystyle \sum _{i}|\pi _{i}(E)|\leq 2M}" loading="lazy">.

By the <a href="Inequality_of_arithmetic_and_geometric_means" class="mw-redirect" title="Inequality of arithmetic and geometric means">inequality of arithmetic and geometric means</a>, we have <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |E|\leq \left({\frac {2}{3}}M\right)^{3/2}}">

</mrow>

</mrow>

<msup>

<mrow>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |E|\leq \left({\frac {2}{3}}M\right)^{3/2}}</annotation>

</semantics>

</math><img src="./900461c82e2dc8c168b486d724da3debdaa6e62e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.728ex; height:6.676ex;" alt="{\displaystyle |E|\leq \left({\frac {2}{3}}M\right)^{3/2}}" loading="lazy">, with extremum reached when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{i}(E)={\frac {2}{3}}M}">

<msub>

</mrow>

</msub>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}(E)={\frac {2}{3}}M}</annotation>

</semantics>

</math><img src="./45ec0a9e647df93d2ba331ee454890bbb6b8df0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:13.249ex; height:5.176ex;" alt="{\displaystyle \pi _{i}(E)={\frac {2}{3}}M}" loading="lazy">.

Thus the arithmetic intensity is bounded above by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle CM^{1/2}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle CM^{1/2}}</annotation>

</semantics>

</math><img src="./bcba0c647b729caccc995dd7643acb35000fd6b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.963ex; height:2.843ex;" alt="{\displaystyle CM^{1/2}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C=(2/3)^{3/2}}">

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C=(2/3)^{3/2}}</annotation>

</semantics>

</math><img src="./7d712c0b73a35888466f84d0a0bb294d90f89c58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.86ex; height:3.343ex;" alt="{\displaystyle C=(2/3)^{3/2}}" loading="lazy">, and so the communication is bounded below by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {nmk}{CM^{1/2}}}}">

<mfrac>

<mrow>

</mrow>

<mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {nmk}{CM^{1/2}}}}</annotation>

</semantics>

</math><img src="./b83cc1f050120ae58c534d149019996bf5473907.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:7.799ex; height:5.843ex;" alt="{\displaystyle {\frac {nmk}{CM^{1/2}}}}" loading="lazy">.

Direct computation verifies that the tiling matrix multiplication algorithm reaches the lower bound.

</div>

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

Consider the following running-time model:<a href="#cite_note-Demmel_2-5">[5]</a>

<ul><li>Measure of computation = Time per <a href="FLOP" class="mw-redirect" title="FLOP">FLOP</a> = γ</li>

<li>Measure of communication = No. of words of data moved = β</li></ul>

⇒ Total running time = γ·(no. of <a href="FLOP" class="mw-redirect" title="FLOP">FLOPs</a>) + β·(no. of words)

From the fact that β >> γ as measured in time and energy, communication cost dominates computation cost. Technological trends<a href="#cite_note-DARPA_2008-6">[6]</a> indicate that the relative cost of communication is increasing on a variety of platforms, from <a href="Cloud_computing" title="Cloud computing">cloud computing</a> to <a href="Supercomputers" class="mw-redirect" title="Supercomputers">supercomputers</a> to mobile devices. The report also predicts that gap between <a href="DRAM" class="mw-redirect" title="DRAM">DRAM</a> access time and FLOPs will increase 100× over coming decade to balance power usage between processors and DRAM.<a href="#cite_note-Demmel_2012-1">[1]</a>

<th>DRAM bandwidth (β)</th>

<th>Network bandwidth (β)

</th></tr>

<tr>

<td>26% / year

</td></tr></tbody></table>

Energy consumption increases by orders of magnitude as we go higher in the memory hierarchy.<a href="#cite_note-Shalf_2010-7">[7]</a>

United States president Barack Obama cited communication-avoiding algorithms in the FY 2012 Department of Energy budget request to Congress:<a href="#cite_note-Demmel_2012-1">[1]</a> <style data-mw-deduplicate="TemplateStyles:r1244412712">

/* start https://en.wikipedia.org/ */

.mw-parser-output .templatequote{overflow:hidden;margin:1em 0;padding:0 32px}.mw-parser-output .templatequotecite{line-height:1.5em;text-align:left;margin-top:0}@media(min-width:500px){.mw-parser-output .templatequotecite{padding-left:1.6em}}

/* end https://en.wikipedia.org/ */

</style><blockquote class="templatequote">New Algorithm Improves Performance and Accuracy on Extreme-Scale Computing Systems. On modern computer architectures, communication between processors takes longer than the performance of a <a href="Floating-point_arithmetic" title="Floating-point arithmetic">floating-point arithmetic</a> operation by a given processor. ASCR researchers have developed a new method, derived from commonly used linear algebra methods, to minimize communications between processors and the memory hierarchy, by reformulating the communication patterns specified within the algorithm. This method has been implemented in the TRILINOS framework, a highly-regarded suite of software, which provides functionality for researchers around the world to solve large scale, complex multi-physics problems.</blockquote>

<div class="mw-heading mw-heading2"><h2 id="Objectives">Objectives</h2></div>

Communication-avoiding algorithms are designed with the following objectives:

<ul><li>Reorganize algorithms to reduce communication across all memory hierarchies.</li>

<li>Attain the lower-bound on communication when possible.</li></ul>

The following simple example<a href="#cite_note-Demmel_2012-1">[1]</a> demonstrates how these are achieved.

<div class="mw-heading mw-heading3"><h3 id="Matrix_multiplication_example">Matrix multiplication example</h3></div>

Let A, B and C be square matrices of order n × n. The following naive algorithm implements C = C + A * B:

<pre> for i = 1 to n

for j = 1 to n

for k = 1 to n

C(i,j) = C(i,j) + A(i,k) * B(k,j)

</pre>

Arithmetic cost (time-complexity): n2(2n − 1) for sufficiently large n or O(n3).

Rewriting this algorithm with communication cost labelled at each step

<pre> for i = 1 to n

{read row i of A into fast memory} - n2 reads

for j = 1 to n

{read C(i,j) into fast memory} - n2 reads

{read column j of B into fast memory} - n3 reads

for k = 1 to n

C(i,j) = C(i,j) + A(i,k) * B(k,j)

{write C(i,j) back to slow memory} - n2 writes

</pre>

Fast memory may be defined as the local processor memory (<a href="CPU_cache" title="CPU cache">CPU cache</a>) of size M and slow memory may be defined as the DRAM.

Communication cost (reads/writes): n3 + 3n2 or O(n3)

Since total running time = γ·O(n3) + β·O(n3) and β >> γ the communication cost is dominant. The blocked (tiled) matrix multiplication algorithm<a href="#cite_note-Demmel_2012-1">[1]</a> reduces this dominant term:

<div class="mw-heading mw-heading4"><h4 id="Blocked_(tiled)_matrix_multiplication">Blocked (tiled) matrix multiplication</h4></div>

Consider A, B and C to be n/b-by-n/b matrices of b-by-b sub-blocks where b is called the block size; assume three b-by-b blocks fit in fast memory.

<pre> for i = 1 to n/b

for j = 1 to n/b

{read block C(i,j) into fast memory} - b2 × (n/b)2 = n2 reads

for k = 1 to n/b

{read block A(i,k) into fast memory} - b2 × (n/b)3 = n3/b reads

{read block B(k,j) into fast memory} - b2 × (n/b)3 = n3/b reads

C(i,j) = C(i,j) + A(i,k) * B(k,j) - {do a matrix multiply on blocks}

{write block C(i,j) back to slow memory} - b2 × (n/b)2 = n2 writes

</pre>

Communication cost: 2n3/b + 2n2 reads/writes << 2n3 arithmetic cost

Making b as large possible:

we achieve the following communication lower bound:

<dl><dd>31/2n3/M1/2 + 2n2 or Ω (no. of FLOPs / M1/2)</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Previous_approaches_for_reducing_communication">Previous approaches for reducing communication</h2></div>

Most of the approaches investigated in the past to address this problem rely on scheduling or tuning techniques that aim at overlapping communication with computation. However, this approach can lead to an improvement of at most a factor of two. Ghosting is a different technique for reducing communication, in which a processor stores and computes redundantly data from neighboring processors for future computations. <a href="Cache-oblivious_algorithm" title="Cache-oblivious algorithm">Cache-oblivious algorithms</a> represent a different approach introduced in 1999 for <a href="Fast_Fourier_transform" title="Fast Fourier transform">fast Fourier transforms</a>,<a href="#cite_note-Frigo_1999-8">[8]</a> and then extended to graph algorithms, dynamic programming, etc. They were also applied to several operations in linear algebra<a href="#cite_note-Toledo_1997-9">[9]</a><a href="#cite_note-Gustavson_1997-10">[10]</a><a href="#cite_note-Elmroth_2004-11">[11]</a> as dense LU and QR factorizations. The design of architecture specific algorithms is another approach that can be used for reducing the communication in parallel algorithms, and there are many examples in the literature of algorithms that are adapted to a given communication topology.<a href="#cite_note-Grigori_2014-12">[12]</a>

<ul><li><a href="Data_locality" class="mw-redirect" title="Data locality">Data locality</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-Demmel_2012-1">^ <a href="#cite_ref-Demmel_2012_1-0">a</a> <a href="#cite_ref-Demmel_2012_1-1">b</a> <a href="#cite_ref-Demmel_2012_1-2">c</a> <a href="#cite_ref-Demmel_2012_1-3">d</a> <a href="#cite_ref-Demmel_2012_1-4">e</a> Demmel, Jim. "Communication avoiding algorithms". 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 2012.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFJia-WeiKung1981" class="citation book cs1">Jia-Wei, Hong; Kung, H. T. (1981). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1145/800076.802486">"I/O complexity"</a>. Proceedings of the thirteenth annual ACM symposium on Theory of computing - STOC '81. New York, New York, USA: ACM Press. pp. 326–333. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F800076.802486">10.1145/800076.802486</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8410593">8410593</a>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFBallardCarsonDemmelHoemmen2014" class="citation journal cs1">Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O. (May 2014). <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1017/s0962492914000038">"Communication lower bounds and optimal algorithms for numerical linear algebra"</a>. Acta Numerica. 23: 1–155. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2Fs0962492914000038">10.1017/s0962492914000038</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0962-4929">0962-4929</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:122513943">122513943</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFDemmelDinh2018" class="citation arxiv cs1">Demmel, James; Dinh, Grace (2018-04-24). "Communication-Optimal Convolutional Neural Nets". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1802.06905">1802.06905</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.DS">cs.DS</a>].</cite>

</li>

<li id="cite_note-Demmel_2-5"><a href="#cite_ref-Demmel_2_5-0">^</a> Demmel, James, and Kathy Yelick. "Communication Avoiding (CA) and Other Innovative Algorithms". The Berkeley Par Lab: Progress in the Parallel Computing Landscape: 243–250.

</li>

<li id="cite_note-DARPA_2008-6"><a href="#cite_ref-DARPA_2008_6-0">^</a> Bergman, Keren, et al. "<a rel="nofollow" class="external text" href="http://staff.kfupm.edu.sa/ics/ahkhan/Resources/Articles/ExaScale%20Computing/TR-2008-13.pdf">Exascale computing study: Technology challenges in exascale computing systems</a>." <a href="Defense_Advanced_Research_Projects_Agency" class="mw-redirect" title="Defense Advanced Research Projects Agency">Defense Advanced Research Projects Agency</a> <a href="Information_Processing_Techniques_Office" title="Information Processing Techniques Office">Information Processing Techniques Office</a> (DARPA IPTO), Tech. Rep 15 (2008).

</li>

<li id="cite_note-Shalf_2010-7"><a href="#cite_ref-Shalf_2010_7-0">^</a> Shalf, John, Sudip Dosanjh, and John Morrison. "Exascale computing technology challenges". High Performance Computing for Computational Science–VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.

</li>

<li id="cite_note-Frigo_1999-8"><a href="#cite_ref-Frigo_1999_8-0">^</a> M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran, "Cacheoblivious algorithms", In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999. IEEE Computer Society.

</li>

<li id="cite_note-Toledo_1997-9"><a href="#cite_ref-Toledo_1997_9-0">^</a> S. Toledo, "<a rel="nofollow" class="external text" href="https://web.archive.org/web/20180102191420/https://pdfs.semanticscholar.org/d198/43912d46f6a25de815eadb1fb43d5ca6f61c.pdf">Locality of reference in LU Decomposition with partial pivoting</a>," SIAM J. Matrix Anal. Appl., vol. 18, no. 4, 1997.

</li>

<li id="cite_note-Gustavson_1997-10"><a href="#cite_ref-Gustavson_1997_10-0">^</a> F. Gustavson, "Recursion Leads to Automatic Variable Blocking for Dense Linear-Algebra Algorithms," IBM Journal of Research and Development, vol. 41, no. 6, pp. 737–755, 1997.

</li>

<li id="cite_note-Elmroth_2004-11"><a href="#cite_ref-Elmroth_2004_11-0">^</a> E. Elmroth, F. Gustavson, I. Jonsson, and B. Kagstrom, "<a rel="nofollow" class="external text" href="http://www.csc.kth.se/utbildning/kth/kurser/2D1253/matalg06/SIR000003.pdf">Recursive blocked algorithms and hybrid data structures for dense matrix library software</a>," SIAM Review, vol. 46, no. 1, pp. 3–45, 2004.

</li>

<li id="cite_note-Grigori_2014-12"><a href="#cite_ref-Grigori_2014_12-0">^</a> <a href="Laura_Grigori" title="Laura Grigori">Grigori, Laura</a>. "<a rel="nofollow" class="external text" href="http://www.lifl.fr/jncf2014/files/lecture-notes/grigori.pdf">Introduction to communication avoiding linear algebra algorithms in high performance computing</a>.

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-20" href="https://en.wikipedia.org/wiki/?title=Communication-avoiding_algorithm&oldid=1296435282">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>